package com.liezh.structurealgorithm;

/**
 * 动态规划： 如在一个图上找最短路径，最长子串查找
 * 因为最短路径，其实就是这个图的最优解，也就是每一步都是最短的路径组成的结果集
 * 所以每一步求解其实是可以拆分的，符合动态规划的第一原则   有最优子结构
 * 而且每一步都不可回溯，后续结果不会对历史结果产生影响     无后效性
 * 子结果叠加才是最终结果                             有重叠子问题
 *
 * 倒推出最优解，从结果出发，每一步都最优，则取得最优结果
 * @author liezh
 * @date 2020-10-10
 */
public class DynamicProgramming {


    public static int minPath1(int[][] matrix) {
        return process1(matrix, matrix[0].length-1);
    }

    /**
     * 递归
     * @param matrix
     * @param i
     * @return
     */
    public static int process1(int[][] matrix, int i) {
        // 到达A退出递归
        if (i == 0) {
            return 0;
        }
        // 状态转移
        else {
            // 设置默认最优值，如果
            int distance = 999;
            for(int j=0; j<i; j++){
                if(matrix[j][i]!=0){
                    int d_tmp = matrix[j][i] + process1(matrix, j);
                    if (d_tmp < distance){
                        distance = d_tmp;
                    }
                }
            }
            return distance;
        }
    }
    public static void main(String[] args) {
        int[][] m = {{0,5,3,0,0,0,0,0,0,0,0,0,0,0,0,0},{0,0,0,1,3,6,0,0,0,0,0,0,0,0,0,0},{0,0,0,0,8,7,6,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,6,8,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,3,5,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,3,3,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,8,4,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0,2,2,0,0,0,0},{0,0,0,0,0,0,0,0,0,0,0,1,2,0,0,0},{0,0,0,0,0,0,0,0,0,0,0,3,3,0,0,0},{0,0,0,0,0,0,0,0,0,0,0,0,0,3,5,0},{0,0,0,0,0,0,0,0,0,0,0,0,0,5,2,0},{0,0,0,0,0,0,0,0,0,0,0,0,0,6,6,0},{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,4},{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,3}};
        System.out.println(minPath1(m));
    }



}
